package com.hyacinth.structure;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 根据key排序的Map
 * 效率没有TreeMap高，推荐使用TreeMap
 * @author zhangfb
 * @version 1.0.0.1
 * @since JDK 1.8
 */
public class SortArrayMap {

    /**节点数组**/
    private Node[] buckets;
    /**节点数组初始大小**/
    private static final int DEFAULT_SIZE = 10;
    /**节点数组真实大小**/
    private int size;

    public SortArrayMap() {
        buckets = new Node[DEFAULT_SIZE];
    }

    /**
     * 写入
     * @param key   键
     * @param value 值
     */
    public void add(Long key, String value) {
        // 检查数组大小
        checkSize(size + 1);
        // 创建节点
        Node node = new Node(key, value);
        // 写入节点数组
        buckets[size++] = node;
    }

    /**
     * 校验是否需要扩容
     * @param size 当前真实容量 + 1
     */
    private void checkSize(int size) {
        if (size >= buckets.length) { // 当前真实容量+1,所以条件是>=
            // 扩容原数组长度的3/2
            int oldLen = buckets.length;
            int newLen = oldLen + oldLen >> 1;
            buckets = Arrays.copyOf(buckets, newLen);
        }
    }

    /**
     * 顺时针取出第一个大于key值的value
     * @param key 条件
     * @return 第一个大于key值的value
     */
    public String firstNodeValue(Long key) {
        if (size == 0) {
            return null;
        }
        for (Node node : buckets) {
            if (node == null) {
                continue;
            }
            if (node.key >= key) {
                return node.value;
            }
        }
        return buckets[0].value;
    }

    /**
     * 排序
     */
    public void sort() {
        Arrays.sort(buckets, 0, size, (o1, o2) -> o1.key > o2.key ? 1 : -1);
    }

    /**
     * 数据节点
     */
    private class Node {
        private Long key;
        private String value;

        public Node(Long key, String value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node{" + "key=" + key +
                    ", value='" + value + '\'' +
                    '}';
        }
    }

    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        map.put(9, "1");
        map.put(2, "1");
        map.put(3, "1");
        map.put(4, "1");
        map.put(6, "1");
        System.out.println(map.toString());
    }
}
